/*
 * @lc app=leetcode.cn id=416 lang=cpp
 *
 * [416] 分割等和子集
 *
 * https://leetcode.cn/problems/partition-equal-subset-sum/description/
 *
 * algorithms
 * Medium (51.67%)
 * Likes:    1296
 * Dislikes: 0
 * Total Accepted:    262K
 * Total Submissions: 507.1K
 * Testcase Example:  '[1,5,11,5]'
 *
 * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [1,5,11,5]
 * 输出：true
 * 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [1,2,3,5]
 * 输出：false
 * 解释：数组不能分割成两个元素和相等的子集。
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * 1 
 * 
 * 
 */

// @lc code=start
class Solution {
// public:
//     bool canPartition(vector<int>& nums) {
//         // weight = nums
//         // value = nums

//         // dp[j] 表示的是容量为j的背包，所背的物品价值最大为dp[j]
//         // dp[j] 表示的是背包总容量是j,最大可以凑成j的子集总和是dp[j]
//         // 根据题意，1 <= nums.length <= 200
//         //          1 <= nums[i] <= 100
//         // 也就是总和最大是20000，那么需要一个10001空间的背包，所有值初始化为0
//         vector<int> dp(10001, 0);
        
//         int sum = 0;
//         for(int i = 0; i < nums.size(); i++) {
//             sum += nums[i];
//         }
//         if(sum % 2 == 1) return false;
//         int target = sum / 2;

//         for(int i = 0; i < nums.size(); i++) {
//             for(int j = target; j >= nums[i]; j--) {
//                 dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
//                 // if(dp[j] == target) return true;
//             }
//         }

//         if(dp[target] == target) return true;
//         return false;
//     }

public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if(sum % 2) return false;
        int target = sum / 2;

        vector<int> dp(target+1, 0);
        
        for(int i = 0; i < nums.size(); i++) {
            for(int j = target; j >= nums[i]; j--) {
                dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
            }
        }

        if(dp[target] == target) return true;
        else return false;
    }

};
// @lc code=end

